#include <stdio.h>

/**
 * @brief 冒泡排序函数，时间复杂度O(n^2)，空间复杂度O(1)，适合小规模数据排序
 * @param arr 待排序数组
 * @param n 数组长度
 * @return 0表示成功，-1表示失败
 */
int bubbleSort(int arr[], int n)
{
  // 参数验证
  if (arr == NULL || n <= 0)
  {
    return -1; // 返回错误码
  }

  int i, j, temp;
  int swapped; // 用于优化的标志位

  for (i = 0; i < n - 1; i++)
  {
    swapped = 0; // 每轮开始前重置标志位

    // Last i elements are already in place
    for (j = 0; j < n - i - 1; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        // swap arr[j] and arr[j+1]
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = 1; // 标记发生了交换
      }
    }

    // 如果这一轮没有发生交换，说明数组已经有序
    if (swapped == 0)
    {
      break;
    }
  }

  return 0; // 成功返回
}

int main()
{
  int arr[] = {64, 34, 25, 12, 22, 11, 90};
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, n);
  printf("Sorted array: \n");
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  return 0;
}